package advance.day05;

/**
 * 描述：
 * 二叉树中一个节点到另一个结点的最长路径
 *
 * @author hl
 * @version 1.0
 * @date 2020/11/10 15:27
 */
public class MaxDistanceInTree {

    public static int maxDistanceInTree(Node head) {
        return process(head).maxPath;
    }

    public static class ReturnType {
        int h;
        int maxPath;

        public ReturnType(int h, int maxPath) {
            this.h = h;
            this.maxPath = maxPath;
        }
    }

    public static ReturnType process(Node head) {
        if (head == null) {
            return new ReturnType(0, 0);
        }
        ReturnType leftInfo = process(head.left);
        ReturnType rightInfo = process(head.right);

        int h = Math.max(leftInfo.h, rightInfo.h) + 1;
        int maxPath = Math.max(Math.max(leftInfo.maxPath, rightInfo.maxPath),
                leftInfo.h + rightInfo.h - 1);
        return new ReturnType(h, maxPath);
    }
}
